package leetcode.sword;

import datastruct.tree.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Z字形打印
 */
public class Solution32_3 {

    public List<List<Integer>> levelOrder(TreeNode root) {

        LinkedList<LinkedList<Integer>> all = new LinkedList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        if(root!=null) queue.add(root);
        boolean leftToRight = true;
        while (!queue.isEmpty()){
            LinkedList<Integer> curLevel = new LinkedList<>();
            int tmp = queue.size();
            for (int i = 0; i < tmp; i++) {
                TreeNode curNode = queue.poll();
                if(leftToRight) curLevel.addLast(curNode.val);
                else curLevel.addFirst(curNode.val);
                if(curNode.left!=null) queue.add(curNode.left);
                if(curNode.right!=null) queue.add(curNode.right);
            }
            all.add(curLevel);
            leftToRight = !leftToRight;
        }
        return (List)all;
    }
}
